#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/8/21 17:43
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 中级-从前序与中序遍历序列构造二叉树.py
# @Software: PyCharm

# Definition for a binary tree node.


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        root = None

        def work(preorder, inorder):
            if len(preorder) <= 0:
                return None
            x = preorder[0]
            nd = TreeNode(x)
            i = inorder.index(x)
            l = len(inorder)
            nd.left = work(preorder[1:i+1], inorder[:i])
            nd.right = work(preorder[i+1:], inorder[i+1:])
            return nd
        return work(preorder, inorder)


def display(nd, dp=0):
    if not nd:
        return
    print(' '*dp, nd.val)
    display(nd.left, dp+1)
    display(nd.right, dp+1)


def main():
    solve = Solution()
    preorder = [3, 9, 20, 15, 7]
    inorder = [9, 3, 15, 20, 7]
    root = solve.buildTree(preorder, inorder)
    display(root)


if __name__ == '__main__':
    main()
